package 动态规划9月;
// https://leetcode-cn.com/problems/split-linked-list-in-parts/
public class 链表725分隔链表0922 {

     public class ListNode {
         int val;
         ListNode next;
         ListNode() {}
         ListNode(int val) { this.val = val; }
         ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     }

    class Solution {
        public ListNode[] splitListToParts(ListNode head, int k) {
            int n = 0;
            ListNode temp = head;
            while (temp != null) {
                n++;
                temp = temp.next;
            }
            int quotient = n / k,////等分链的长度
                    remainder = n % k;//如果能等分，算出等分后剩余的候补节点
            //
            ListNode[] parts = new ListNode[k];
            //回到头结点
            ListNode curr = head;
            for (int i = 0; i < k && curr != null; i++) {
                //初始化的时候把每一个等分链的头结点存到数组下标
                parts[i] = curr;
                //算出每个等分该存储的长度
                int partSize = quotient + (i < remainder ? 1 : 0);
                //把除头节点剩余节点接到当前头结点的后面
                for (int j = 1; j < partSize; j++) {
                    curr = curr.next;
                }
                //断链前保存断链的下一个结点
                ListNode next = curr.next;
                //断链
                curr.next = null;
                //新结点
                curr = next;
            }
            return parts;
        }
    }

}
